#include <stdio.h>
#include <stdlib.h>
#define NAMESIZE 2
#define MAPSIZE 16
//Construct a MapLib Structure, including:
struct MapLib{ 
 int mapsize; // size of map;
 char landname[MAPSIZE][NAMESIZE]; // names of lands on the map such as CA LA or NY;
 int matrix[MAPSIZE][MAPSIZE]; // the matrix indicating the boundaries between lands;
 int color[MAPSIZE]; //the series indicating the color of each land with specific num.
 };
typedef struct MapLib *PMapLib;
//Detecting whether the coloring is finished.
int isFinish(PMapLib sample) { 
 int i = 0;
 while (i<sample->mapsize) {
  if (sample->color[i]==0) {
   return 0;
   }
  i++;
  }
 return 1;
 }
//Detecting whether the num land can be colored with "color"; 
int notAdjWith (int color, PMapLib sample, int num) {  
 int i = 0;
 while (i<sample->mapsize) {
   if (sample->color[i]==color) { //of current color
    if (sample->matrix[num][i]==1) { //if it is adjacent to current land.
     return 0;
     }
    }
  i++;
  }
 return 1;
 }
//To color up the sample map, return the num of colors that were used.
int colorUp (PMapLib sample) {
 int color = 0;
 while (!isFinish(sample)) {
  color++;
  int i=0;
  for (i=0;i<sample->mapsize;i++) {
   if (notAdjWith(color, sample, i)&&sample->color[i]==0) { 
    sample->color[i]=color;  //If no adjacent-same-color land found, then color it.
    }
   }
 }
 return color; 
 } 
//To generate the map, from "landlist.dat" with land names,
//and "matrix.dat" with boundary matrix.
PMapLib generateMap (int mapsize) {
 int i=0,j=0;
 PMapLib map=(PMapLib)malloc(sizeof(struct MapLib));
 map->mapsize=mapsize;
 
 FILE *fr;
 FILE *fr_m;
 fr = fopen("landlist.dat","rt");
 fr_m = fopen("matrix.dat","rt");
 
 char landlist[MAPSIZE][NAMESIZE];
 int matrix[MAPSIZE][MAPSIZE];
 char separate;
//Firstly, the data are put into  "landlist" and "matrix".
//Input file contains lands' name separated by one byte.
 for(i=0;i<mapsize&&separate!=EOF;i++) {   
   for (j=0;j<NAMESIZE;j++) {
    landlist[i][j]=fgetc(fr);
    }
   separate=fgetc(fr);
   }
 for(i=0;i<mapsize;i++) {
   for (j=0;j<mapsize;j++) {
    matrix[i][j]=0; //Initialization of the matrix
    }
   }
 for(i=0;i<mapsize;i++) {
   for (j=0;j<=i;j++) {
    matrix[i][j]=fgetc(fr_m)-'0';
    matrix[j][i]=matrix[i][j]; //One can just input lower left half of the matrix.
    }
  char temp=fgetc(fr_m); 
  if (temp=='\n') continue;
   }
   
 for(i=0;i<mapsize;i++) {
   for (j=0;j<NAMESIZE;j++) {
    map->landname[i][j]=landlist[i][j]; //Transfer names from landlist to sample map.
    }
   map->color[i]=0;        //Initial color should be 0.
   }
   
 for(i=0;i<mapsize;i++) {
   for (j=0;j<i;j++) {
    if (matrix[i][j]!=0&&matrix[i][j]!=1) {
     printf ("Illegal matrix input.");
     }//report the error if the element of matrix is not 1 or 0.
    map->matrix[i][j]=matrix[i][j];//Transfer elements from matrix to sample map matrix.
    map->matrix[j][i]=matrix[i][j]; 
    }
   }
   return map;
 }
//Function to output the color result. 
int outputColoredMap (PMapLib sample) {
 int i,j,color;
 int colornum=colorUp(sample);
 printf("\n%d colors used.",colornum);
 for (color=1;color<=colornum;color++) {
  printf("\nColor %d: ",color);
  for (i=0;i<sample->mapsize;i++) {
   if(sample->color[i]==color) {
    for (j=0;j<NAMESIZE;j++) {
     printf("%c",sample->landname[i][j]);
     }
    printf(" ");
    }
   }
  }
 printf("\n");
 }

int main()
{
 PMapLib map;
 int temptest;
 int mapsize;
 mapsize=temptest=16; 
 map = generateMap(mapsize);
 int i,j;
 
   outputColoredMap(map);
   
  system("PAUSE"); 
  return 0;
}

